<?php

/*class C {

	public $tree = array();

	public function getAsArray($str){
		if($str!='/'){
			$length = strlen($str);
			$elements = array();
			$element = "";
			$oldchar = "";
			$j = 0;
			for($i=0;$i<$length;$i++){
				$char = substr($str, $i, 1);
				if($char!='/'&&$oldchar!="\\"){
					$element.=$char;
				} else {
					if($j==0){
						if($element!=""){
							$elements[] = $element;
						}
					} else {
						$elements[] = $element;
					}
					$element = "";
					$j++;
				}
			}
			if($j==0){
				if($element!=""){
					$elements[] = $element;
				}
			} else {
				$elements[] = $element;
			}
		} else {
			$elements = array();
		}
		return $elements;
	}

	public function getNodeByPath($path){
		$elements = $this->getAsArray($path);
		$ce = count($elements);
		if($ce>0){
			$ep = $ce - 1;
			$path = &$this->tree;
			for($i=0;$i<$ce;$i++){
				if($i!=$ep){
					if(!isset($path[$elements[$i]])){
						$path[$elements[$i]] = array();
					}
					$path = &$path[$elements[$i]];
				}
			}

			$i--;
			if(isset($path[$elements[$i]])){
				$path = &$path[$elements[$i]];
			} else {
				if(in_array($elements[$i], $path)){
					$cp = count($path);
					for($j=0;$j<$cp;$j++){
						if($path[$j]==$elements[$i]){
							$path[$elements[$i]] = array();
							unset($path[$j]);
							break;
						}
					}
				} else {
					$path[$elements[$i]] = array();
				}
				$path = &$path[$elements[$i]];
			}
		} else {
			$path = &$this->tree;
		}
		return $path;
	}

	public function add($elements, $items){
		$elements = $this->getAsArray($elements);
		$it = array();
		$it = &$p;
		$ci = count($items);
		$ip = $ci - 1;
		for($i=0;$i<$ci;$i++){
			if($i!=$ip){
				if(!isset($p[$items[$i]])){
					$p[$items[$i]] = array();
				}
				$p = &$p[$items[$i]];
			}
		}
		$i--;
		$p[] = $items[$i];

		$ce = count($elements);
		if($ce>0){
			$ep = $ce - 1;
			$path = &$this->tree;
			for($i=0;$i<$ce;$i++){
				if($i!=$ep){
					if(!isset($path[$elements[$i]])){
						$path[$elements[$i]] = array();
					}
					$path = &$path[$elements[$i]];
				}
			}

			$i--;
			if(isset($path[$elements[$i]])){
				$path = &$path[$elements[$i]];
			} else {
				if(in_array($elements[$i], $path)){
					$cp = count($path);
					for($j=0;$j<$cp;$j++){
						if($path[$j]==$elements[$i]){
							$path[$elements[$i]] = array();
							unset($path[$j]);
							break;
						}
					}
				} else {
					$path[$elements[$i]] = array();
				}
				$path = &$path[$elements[$i]];
			}
		} else {
			$path = &$this->tree;
		}
		$path = array_merge_recursive($path, $it);
		return $this->tree;
	}


}

$c = new C();
$c->add("/a/b/c", array("d", "e"));
$c->add("/a/b", array("x", "y"));
$c->add("/a", array("w", "s"));
$c->add("/", array("w", "s"));
$c->add("/w/s", array("j", new stdClass()));

$node = $c->getNodeByPath("/a/b");
print_r($node);*/
/*
node =
id
node_id
key
value

attributes =
node_id
key
attributes

$data

*/

class B {

	private $id = 0;
	public $data = array();
	public $indexKey = array();
	public $indexNode = array();
	public $indexLevel = array();

	public function getAsArray($str){
		if($str!='/'){
			$length = strlen($str);
			$elements = array();
			$element = "";
			$oldchar = "";
			$j = 0;
			for($i=0;$i<$length;$i++){
				$char = substr($str, $i, 1);
				if($char!='/'&&$oldchar!="\\"){
					$element.=$char;
				} else {
					if($j==0){
						if($element!=""){
							$elements[] = $element;
						}
					} else {
						$elements[] = $element;
					}
					$element = "";
					$j++;
				}
			}
			if($j==0){
				if($element!=""){
					$elements[] = $element;
				}
			} else {
				$elements[] = $element;
			}
		} else {
			$elements = array();
		}
		return $elements;
	}

	function addNode($parent, $level, $key){
		$this->id++;
		$this->data[$this->id] = array(
			'id' => $this->id,
			'node_id' => $parent,
			'level' => $level,
			'key' => $key
		);
		if(!isset($this->indexKey[$key])){
			$this->indexKey[$key] = array();
		}
		$this->indexKey[$key][] = $this->id;
		if(!isset($this->indexNode[$parent])){
			$this->indexNode[$parent] = array();
		}
		$this->indexNode[$parent][] = $this->id;
		if(!isset($this->indexLevel[$level])){
			$this->indexLevel[$level] = array();
		}
		$this->indexLevel[$level][] = $this->id;
		return $this->id;
	}

	public function add($elements, $items){
		$elements = $this->getAsArray($elements);
		$ce = count($elements);
		$level = 0;
		$node_id = 0;
		$leaf = null;
		for($i=0;$i<$ce;$i++){
			$found = false;
			if(isset($this->indexKey[$elements[$i]])){
				foreach($this->indexKey[$elements[$i]] as $id){
					$row = &$this->data[$id];
					if($row['level']==$level){
						$found = true;
						$node_id = $row['id'];
						$level = $row['level']+1;
						$leaf = &$row;
						break;
					}
				}
			}
			if($found==false){
				$node_id = $this->addNode($node_id, $level, $elements[$i]);
				$leaf = &$this->data[$node_id];
				$level++;
			}
		}
		$node_id = $leaf['id'];
		$level = $leaf['level']+1;
		$ci = count($items);
		for($i=0;$i<$ci;$i++){
			$found = false;
			if(isset($this->indexKey[$items[$i]])){
				foreach($this->indexKey[$items[$i]] as $id){
					$row = &$this->data[$id];
					if($row['level']==$level){
						$found = true;
						$node_id = $row['id'];
						$level = $row['level']+1;
						$leaf = &$row;
						break;
					}
				}
			}
			if($found==false){
				$node_id = $this->addNode($node_id, $level, $items[$i]);
				$leaf = &$this->data[$node_id];
				$level++;
			}
		}
		#print_r($this->data);
	}

	public function query($elements){
		$elements = $this->getAsArray($elements);
		$ce = count($elements);
		$level = 0;
		$node_id = 0;
		$leaf = null;
		for($i=0;$i<$ce;$i++){
			$found = false;
			if(isset($this->indexKey[$elements[$i]])){
				foreach($this->indexKey[$elements[$i]] as $id){
					$row = &$this->data[$id];
					if($row['level']==$level){
						$found = true;
						$node_id = $row['id'];
						$level = $row['level']+1;
						$leaf = &$row;
						break;
					}
				}
			}
			if($found==false){
				return null;
			}
		}
		return $leaf;
	}

	function tree(){
		for($i=0;$i<=7;$i++){
			if(isset($this->indexLevel[$i])){
				foreach($this->indexLevel[$i] as $id){
					$row = &$this->data[$id];
					print "$i= ".$row['key']." ";
					$keys = array();
					if(isset($this->indexNode[$id])){
						foreach($this->indexNode[$id] as $nid){
							$nrow = &$this->data[$nid];
							$keys[] = $nrow['key'];
						}
						print "-> ".join(", ", $keys)."\n";
					} else {
						print "\n";
					}
				}
			}
		}
	}

}

#$a = microtime(true);
$b = new B();
$b->add("/a/b/c", array("d", "e"));
$b->add("/a/b", array("x", "y"));
$b->add("", array("z", "w"));

#print_r($b->query("/a/b/x"));

#print_r($b->indexLevel);

#print_r($b->indexKey);

$b->tree();

#print_r($b->data);

#print microtime(true)-$a;
#print